package 动态规划.棋盘dp;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/10 19:59
 */
public class lc1289下降最小和II {


    // 只需要关心两侧， 也就是 j 的边界情况就行了！
    public int dfs(int i, int j, int matrix[][], Integer dp[][]) {
//        if (j < 0 || j >= matrix[0].length) {
//            return Integer.MAX_VALUE / 2;
//        }
        if (i == matrix.length - 1) {
            return matrix[i][j];
        }
        if (dp[i][j] != null) {
            return dp[i][j];
        }
        int ans = Integer.MAX_VALUE / 2;
        for (int col = 0; col < matrix[0].length; col++) {
            if (col != j) {
                ans = Math.min(dfs(i + 1, col, matrix, dp), ans);
            }
        }

        return ans;
    }

    // 好像 可以直接 将这个 solve 中的for 循环给省掉， 直接用一个递归就能 dfs就能解决
    public int solve(int matrix[][]) {
        int ans = Integer.MAX_VALUE;
        Integer[][] dp = new Integer[matrix.length][matrix[0].length];
        for (int j = 0; j < matrix[0].length; j++) {
            ans = Math.min(ans, dfs(0, j, matrix, dp));
        }
        return ans;
    }


    /*
    正常记忆化搜索改成 动态规划！
     */

    public int dp(int matrix[][]) {
        int dp[][] = new int[matrix.length][matrix[0].length];
        for (int j = 0; j < matrix[0].length; j++) {
            dp[matrix.length - 1][j] = matrix[matrix.length - 1][j];
        }
        for (int i = matrix.length - 2; i >= 0; i--) {
            for (int j = 0; j < matrix[0].length; j++) {
                int ans = Integer.MAX_VALUE; //
                for (int col = 0; col < matrix[0].length; col++) {
                    if (col != j) {
                        ans = Math.min(dp[i + 1][col], ans);
                    }
                }
                dp[i][j] = ans + matrix[i][j];
            }
        }
        return Arrays.stream(dp[0]).min().getAsInt();
    }

    @Test
    public void test() {
        int matrix[][] = {{7}};
        System.out.println(dp(matrix));
    }


    /*
     斜率优化！
     */
    public int dp1(int matrix[][]) {
        int dp[][] = new int[matrix.length][matrix[0].length];
        for (int j = 0; j < matrix[0].length; j++) {
            dp[matrix.length - 1][j] = matrix[matrix.length - 1][j];
        }
        for (int i = matrix.length - 2; i >= 0; i--) {
            for (int j = 0; j < matrix[0].length; j++) {
                int ans = Integer.MAX_VALUE; //
                for (int col = 0; col < matrix[0].length; col++) {
                    if (col != j) {
                        ans = Math.min(dp[i + 1][col], ans);
                    }
                }
                dp[i][j] = ans + matrix[i][j];
            }
        }
        return Arrays.stream(dp[0]).min().getAsInt();
    }




}
